Lema de pompare

În teoria limbajelor formale, o lemă de pompare spune că orice limbaj dintr-o clasă dată, dacă este "pompat", rămâne neschimbat. Pomparea unui limbaj presupune ca orice șir suficient de lung din limbaj să poată fi împărțit în componente, a căror repetare produce alte șiruri, care vor face parte toate din limbajul respectiv. Astfel, dacă există o lemă de pompare pentru o clasă dată de limbaje, majoritatea limbajelor din acea clasă va conține o mulțime infinită de șiruri finite, toate produse prin regula simplă dată de lemă. În general, asemenea rezultate depind de principiul lui Dirichlet.

Considerente generale

Cele mai importante două exemple sunt lema de pompare pentru limbaje regulate și lema de pompare pentru limbaje independente de context. Spre deosebire de teoreme, lemele sunt gândite în așa fel încât să ușureze demonstrațiile. Aceste două leme sunt adeseori folosite pentru a determina dacă un anumit limbaj nu face parte dintr-o anumită clasă de limbaje. Totuși, ele nu pot fi folosite pentru a determina dacă un limbaj face parte dintr-o clasă de limbaje, deoarece satisfacerea lemei de pompare este o condiție necesară, dar nu suficientă, pentru apartenența la o clasă.

Ca un exemplu de aplicare practică a lemelor de pompare, cineva care cunoaște lema de pompare pentru limbaje regulate poate vedea imediat că un limbaj care permite expresii în paranteze dar impune condiția ca parantezele să fie echilibrate (să se închidă corect), nu poate fi un limbaj regulat, și deci limbajul nu poate fi generat de o gramatică regulată, și nici recunoscut de un automat finit. Încercarea de a realiza o demonstrație a acestui fapt fără a folosi lema ar dura destul de mult.

Lema de pompare pentru limbaje regulate

Dacă un limbaj L este regulat, atunci există un număr p > 0, reprezentând lungimea pompării, astfel încât fiecare șir w din L cu |w| ≥ p poate fi scris sub forma:

w = x y z,

cu șirurile x, y și z respectând relațiile |x y| ≤ p, |y| > 0 și

x y ⁱ z face parte din L, oricare ar fi i ≥ 0.

(Observație: aceasta este trivial adevărată dacă limbajul nu e infinit, deoarece în acest caz p trebuie doar să fie mai mare decât lungimea celui mai lung șir din limbaj).

Utilizare practică

Folosind această lemă, se poate demonstra de exemplu că limbajul L = {a ⁿ b ⁿ : n ≥ 0} peste alfabetul Σ = {a, b} nu este regulat. Pentru că dacă ar fi regulat, am putea alege p cu proprietatea din lema de pompare. Șirul w = a ^p b ^p face parte din L, și lema de pompare garantează că există o descompunere w = x y z cu |x y| ≤ p, |y| ≥ 1 și x y ⁱ z în L, pentru orice i ≥ 0. Dar atunci y trebuie să constea dintr-un număr nenul de a-uri, și nici un b; în acest caz, x y ² z are mai multe a-uri decât b-uri și de aceea nu este din L, contradicție.

Demonstrația că limbajul parantezelor echilibrate (corect închise) nu este regulat merge pe aceeași idee. Dat fiind p, există un șir de paranteze echilibrate care începe cu mai mult de p paranteze deschise, astfel încât y va consta doar din paranteze deschise. Repetând y, putem produce un șir care nici măcar nu mai conține numere egale de paranteze deschise și paranteze închise, și deci acestea nu pot fi echilibrate.

Demonstrația

Ideea de demonstrație pentru lema de pompare este următoarea: limbajul regulat este acceptat de un anumit automat finit acceptor; alegem drept p numărul stărilor acelui acceptor. Fiecare șir mai lung decât p va revizita o anumită stare a automatului, cauzând astfel o buclă ce poate fi repetată (sau nefolosită, pentru i = 0). Etichetele de-a lungul buclei corespund șirului y.

Insuficiența

Observație: Lema de pompare nu dă o condiție suficientă ca un limbaj să fie regulat: de exemplu, limbajul { u u ^R v : u, v $\in$ {0,1}⁺ } (limbajul șirurilor peste alfabetul { 0; 1 } care constau dintr-un palindrom par nevid, urmat de un alt șir nevid) nu este regulat dar tot poate fi "pompat" cu p = 4: Să considerăm un șir w = u u ^R v de lungime cel puțin 4. Dacă u are lungime 1, atunci |v| ≥ 2 și putem lua y ca primul caracter din v. Altfel, luăm y ca fiind ultimul caracter din u, repetat, adică șirul format din cele două caractere din mijlocul șirului u u ^R, pentru care se poate observa că y ^k reprezintă și el un palindrom, deci x y ^k z face parte din limbajul studiat. Pentru un test practic care caracterizează exact limbajele regulate, vezi teorema Myhill-Nerode.

Lema de pompare pentru limbaje independente de context

Dacă un limbaj L este independent de context, atunci există un număr p > 0, reprezentând lungimea pompării, astfel încât orice șir w din L cu proprietatea că |w| ≥ p poate fi scris ca

w = u v x y z

unde șirurile u, v, x, y și z au proprietățile |v x y| ≤ p, |v y| ≥ 1 și

u v ⁱ x y ⁱ z face parte din L pentru orice i ≥ 0.

(Pentru o generalizare a acestei leme, vezi Lema lui Ogden.)

Utilizare practică

Lema de pompare se poate folosi pentru a arăta că anumite limbaje nu sunt independente de context. De exemplu, putem demonstra că limbajul L = { a ⁱ b ⁱ c ⁱ : i > 0 } nu este independent de context.

Presupunem L independent de context
1. Condițiile:
  1. | vxy | ≤ p. Adică porțiunea din mijloc să nu fie prea lungă.
  2. $vy\neq \lambda$ . Pentru că v și y sunt piesele care vor fi "pompate", această condiție impune ca cel puțin unul din șirurile de pompat să nu fie vid.
  3. Pentru orice i ≥ 0, uvⁱxyⁱz face parte din L. Adică cele două șiruri v și y pot fi "pompate" de oricâte ori, inclusiv 0, iar șirul rezulatat va fi în continuare membru al limbajului L.
Dacă șirul $w\in L$ cu | w | > p, înseamnă (conform lemei) că w = uvxyz, unde | vxy | ≤ p
Acum, alegem o valoare pentru o variabilă întreagă i care e mai mare decât p.
Atunci, oricând apare uvxyz în șirul aⁱbⁱcⁱ, vxy nu poate conține mai mult decât două litere diferite, pentru că cel mai din dreapta a este la i+1 poziții depărtare de cel mai din stânga c.
- De ex: Poate fi doar șir de a-uri, doar de b-uri, sau doar de c-uri, sau poate fi de a-uri și b-uri, sau poate fi de b-uri și c-uri.
  - Astfel, șirul vxy nu poate conține mai mult decât două simboluri distincte, dar, conform lemei de pompare, nu poate fi nici vid, deci trebuie să conțină cel puțin un simbol.
Acum putem începe să "pompăm"
1. Deoarece uvxyz face parte din L, uv²xy²z trebuie să facă și el parte din L. Pentru că v și y nu pot fi ambele vide, |uv²xy²z| > |uvxyz|, deci am adăugat simboluri.
2. Dar deoarece vy nu conține toate cele trei litere distincte, nu am avut cum să adăugăm același număr din fiecare literă. Am pompat mai multe litere și am contrazis definiția inițială a lui L. Astfel, uv²xy²z nu poate fi un șir din L.
Am ajuns la o contradicție. De aceea, presupunerea noastră inițială, că L este independent de context, este falsă. q.e.d.

Bibliografie

Michael Sipser - "Introduction to the Theory of Computation", PWS Publishing 1997, ISBN 0-534-94728-X Secțiunea 1.4: Limbaje neregulate, pp.77–83. Secțiunea 2.3: Limbaje neindependente de context, pp.115–119.